#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

TreeNode *createNode(int data) 
{
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

TreeNode *createTree(int arr[], int len) //负数代表节点为空
{
    if (len < 1) return NULL; //arr为空
   
    TreeNode **nodeArr = (TreeNode **)malloc(sizeof(TreeNode *) * len); //二级指针存储节点指针
    memset(nodeArr, 0, sizeof(TreeNode *) * len); //初始化NULL

    nodeArr[0] = createNode(arr[0]); //根指针

    for (int i = 0; i < len; i++) { 
        int l_index = 2 * i +1;
        int r_index = 2 * i +2;
        if (l_index < len && arr[l_index] > 0) {
            nodeArr[l_index] = createNode(arr[l_index]);//创建左节点 
            nodeArr[i]->lchild = nodeArr[l_index];                 
        }
        if (r_index < len && arr[r_index] > 0) {
            nodeArr[r_index] = createNode(arr[r_index]);
            nodeArr[i]->rchild = nodeArr[r_index];
        }
    }
    TreeNode *root = nodeArr[0];
    free(nodeArr);
    return root;
}
void inOrder(TreeNode *root)
{
    if (root) {
        inOrder(root->lchild);
        printf("%d ", root->data);
        inOrder(root->rchild);
    }
}

int main(int argc, char *argv[])
{
    int arr[] = {1, 2, 3, 4, 5, -1, 3, -1, 10};
    int len = sizeof(arr) / sizeof(arr[0]);
    TreeNode *root = createTree(arr, len);
    inOrder(root);

    return 0;
} 